package algo.A03_递归和算法复杂度;

import util.ArrayUtil;

/**
 * 给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。
 * 例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8),返回[5,8]代表下标从5到8是最长递增子序列
 */
public class T13_最长连续递增子序列 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 50);
        ArrayUtil.print(arr);
        int[] result = solution(arr);
        ArrayUtil.print(result);
    }

    private static int[] solution(int[] arr){
        int p_low = 0;//低指针
        int p_high = 0;//高指针
        int[] result = {0,0};//最长递增子序列区间
        while (p_high < arr.length){
            //当高指针指的位置比前一个大，且区间长度大于之前的长度，最长递增子序列区间就要延长
            if (p_high == 0 || arr[p_high] >= arr[p_high - 1]){
                if (p_high - p_low > result[1] - result[0]){
                    result[0] = p_low;
                    result[1] = p_high;
                }
            }else{//如果更小，就要变更低指针的位置为当前高指针指向的下标
                p_low = p_high;
            }
            p_high++;//高指针向后移动
        }
        return result;
    }
}
